/*-----------------
** description:
** Algo C(Comparison counting). This algorithm sorts R[0]~R[N-1] on the keys K[0]~K[N-1]
** by maintaining a auxiliary table COUNT[0]~COUNT[N-1] to count the number of keys
** less than a given key. After the conclusion of the algorithm, COUNT[j]+1 will sepecify
** the final position of record R[j].
**-----------------
** Auther: coanor
** Date:2009.10.11
*/

#include <stdlib.h>
#include <stdio.h>

#define ARR_SZ 16

int main()
{
  int count[ARR_SZ] = {0};
  int count_2[ARR_SZ] = {0};
  int temp[ARR_SZ] = {0};
  int R[ARR_SZ] = {503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703/*,
                     503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703*/
                     };
  int i,j;
  
  /* Origin algorithm C */
  for (i = ARR_SZ - 1; i>0; --i) {
    for (j = i-1; j >=0; --j) {
      if (R[i] == R[j]) {
        if (j < i) {
           if (count[i] > count[j]) {
	     count[j]++;
             printf("count_j++.\n");				       
           } else if (count[i] < count[j]) {
	     count[i]++;
	     printf("count_i++.\n");				        
	   } else {
	     /* now, j < i,R[j]'s position is before R[i]'s,
	     ** we plan to make it a stable sort, so count[i] 
	     ** increase by 1.
	     */
	     count[i]++;
	     printf("Origin: R_j equals to R_i.\n");
	   }
	}
        continue; 
      }
      if (R[i] > R[j])
         count[i]++;
      else
         count[j]++;
    }
  }

  /* print COUNT[N] content */
  for (i = 0; i < ARR_SZ; ++i) {
    printf("%5d ", count[i]+1);
  }
  
  printf("\n");
  
  for (i = 0; i < ARR_SZ; ++i) { 
    temp[count[i]] = R[i];
  }
  /* print origin order */
  for (i = 0; i < ARR_SZ; ++i) {
    printf ("%5d", R[i]);
  }
  
  printf("\n");
  
  /* print last order, depend on COUNT[N] */
  for (i = 0; i < ARR_SZ; ++i) {
    printf ("%5d", temp[i]);
  }
     
  printf("\n");
    
  /* Excercise 1:
  ** i varies from 2 to N.
  ** At the same time, j varies from 1 up to i
  */
  for (i = 0; i < ARR_SZ - 1; ++i) {
    for (j = i + 1; j <= ARR_SZ - 1; ++j) {
      if (R[i] == R[j]) {			   
        continue; 
      }
      if (R[i] > R[j])
        count_2[i]++;
      else
        count_2[j]++;
    }
  }
  for (i = 0; i < ARR_SZ; ++i) {
    /* printf("%2d ", count_2[i]+1)*/;
  }
	
  exit(0);
}
